home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 3 / BBS in a box - Trilogy III.iso / Files / Prog / B-C / Berkeley-yacc-mpw / closure.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-10-14  |  6.2 KB  |  306 lines  |  [TEXT/MPS ]
  1. /*
  2.  * Copyright (c) 1989 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Robert Paul Corbett.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #ifndef lint
  38. static char sccsid[] = "@(#)closure.c    5.2 (Berkeley) 6/1/90";
  39. #endif /* not lint */
  40.  
  41. #include "defs.h"
  42.  
  43. short *itemset;
  44. short *itemsetend;
  45. unsigned *ruleset;
  46.  
  47. static unsigned *first_derives;
  48. static unsigned *EFF;
  49.  
  50.  
  51. set_EFF()
  52. {
  53.     register unsigned *row;
  54.     register int symbol;
  55.     register short *sp;
  56.     register int rowsize;
  57.     register int i;
  58.     register int rule;
  59.  
  60.     rowsize = WORDSIZE(nvars);
  61.     EFF = NEW2(nvars * rowsize, unsigned);
  62.  
  63.     row = EFF;
  64.     for (i = start_symbol; i < nsyms; i++)
  65.     {
  66.     sp = derives[i];
  67.     for (rule = *sp; rule > 0; rule = *++sp)
  68.     {
  69.         symbol = ritem[rrhs[rule]];
  70.         if (ISVAR(symbol))
  71.         {
  72.         symbol -= start_symbol;
  73.         SETBIT(row, symbol);
  74.         }
  75.     }
  76.     row += rowsize;
  77.     }
  78.  
  79.     reflexive_transitive_closure(EFF, nvars);
  80.  
  81. #ifdef    DEBUG
  82.     print_EFF();
  83. #endif
  84. }
  85.  
  86.  
  87. set_first_derives()
  88. {
  89.   register unsigned *rrow;
  90.   register unsigned *vrow;
  91.   register int j;
  92.   register unsigned mask;
  93.   register unsigned cword;
  94.   register short *rp;
  95.  
  96.   int rule;
  97.   int i;
  98.   int rulesetsize;
  99.   int varsetsize;
  100.  
  101.   rulesetsize = WORDSIZE(nrules);
  102.   varsetsize = WORDSIZE(nvars);
  103.   first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
  104.  
  105.   set_EFF();
  106.  
  107.   rrow = first_derives + ntokens * rulesetsize;
  108.   for (i = start_symbol; i < nsyms; i++)
  109.     {
  110.       vrow = EFF + ((i - ntokens) * varsetsize);
  111.       cword = *vrow++;
  112.       mask = 1;
  113.       for (j = start_symbol; j < nsyms; j++)
  114.     {
  115.       if (cword & mask)
  116.         {
  117.           rp = derives[j];
  118.           while ((rule = *rp++) >= 0)
  119.         {
  120.           SETBIT(rrow, rule);
  121.         }
  122.         }
  123.  
  124.       mask <<= 1;
  125.       if (mask == 0)
  126.         {
  127.           cword = *vrow++;
  128.           mask = 1;
  129.         }
  130.     }
  131.  
  132.       vrow += varsetsize;
  133.       rrow += rulesetsize;
  134.     }
  135.  
  136. #ifdef    DEBUG
  137.   print_first_derives();
  138. #endif
  139.  
  140.   FREE(EFF);
  141. }
  142.  
  143.  
  144. closure(nucleus, n)
  145. short *nucleus;
  146. int n;
  147. {
  148.     register int ruleno;
  149.     register unsigned word;
  150.     register unsigned mask;
  151.     register short *csp;
  152.     register unsigned *dsp;
  153.     register unsigned *rsp;
  154.     register int rulesetsize;
  155.  
  156.     short *csend;
  157.     unsigned *rsend;
  158.     int symbol;
  159.     int itemno;
  160.  
  161.     rulesetsize = WORDSIZE(nrules);
  162.     rsp = ruleset;
  163.     rsend = ruleset + rulesetsize;
  164.     for (rsp = ruleset; rsp < rsend; rsp++)
  165.     *rsp = 0;
  166.  
  167.     csend = nucleus + n;
  168.     for (csp = nucleus; csp < csend; ++csp)
  169.     {
  170.     symbol = ritem[*csp];
  171.     if (ISVAR(symbol))
  172.     {
  173.         dsp = first_derives + symbol * rulesetsize;
  174.         rsp = ruleset;
  175.         while (rsp < rsend)
  176.         *rsp++ |= *dsp++;
  177.     }
  178.     }
  179.  
  180.     ruleno = 0;
  181.     itemsetend = itemset;
  182.     csp = nucleus;
  183.     for (rsp = ruleset; rsp < rsend; ++rsp)
  184.     {
  185.     word = *rsp;
  186.     if (word == 0)
  187.         ruleno += BITS_PER_WORD;
  188.     else
  189.     {
  190.         mask = 1;
  191.         while (mask)
  192.         {
  193.         if (word & mask)
  194.         {
  195.             itemno = rrhs[ruleno];
  196.             while (csp < csend && *csp < itemno)
  197.             *itemsetend++ = *csp++;
  198.             *itemsetend++ = itemno;
  199.             while (csp < csend && *csp == itemno)
  200.             ++csp;
  201.         }
  202.  
  203.             mask <<= 1;
  204.             ++ruleno;
  205.         }
  206.     }
  207.     }
  208.  
  209.     while (csp < csend)
  210.     *itemsetend++ = *csp++;
  211.  
  212. #ifdef    DEBUG
  213.   print_closure(n);
  214. #endif
  215. }
  216.  
  217.  
  218.  
  219. finalize_closure()
  220. {
  221.   FREE(itemset);
  222.   FREE(ruleset);
  223.   FREE(first_derives + ntokens * WORDSIZE(nrules));
  224. }
  225.  
  226.  
  227. #ifdef    DEBUG
  228.  
  229. print_closure(n)
  230. int n;
  231. {
  232.   register short *isp;
  233.  
  234.   printf("\n\nn = %d\n\n", n);
  235.   for (isp = itemset; isp < itemsetend; isp++)
  236.     printf("   %d\n", *isp);
  237. }
  238.  
  239.  
  240. print_EFF()
  241. {
  242.     register int i, j, k;
  243.     register unsigned *rowp;
  244.     register unsigned word;
  245.     register unsigned mask;
  246.  
  247.     printf("\n\nEpsilon Free Firsts\n");
  248.  
  249.     for (i = start_symbol; i < nsyms; i++)
  250.     {
  251.     printf("\n%s", symbol_name[i]);
  252.     rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
  253.     word = *rowp++;
  254.  
  255.     mask = 1;
  256.     for (j = 0; j < nvars; j++)
  257.     {
  258.         if (word & mask)
  259.         printf("  %s", symbol_name[start_symbol + j]);
  260.  
  261.         mask <<= 1;
  262.         if (mask == 0)
  263.         {
  264.         word = *rowp++;
  265.         mask = 1;
  266.         }
  267.     }
  268.     }
  269. }
  270.  
  271.  
  272. print_first_derives()
  273. {
  274.   register int i;
  275.   register int j;
  276.   register unsigned *rp;
  277.   register unsigned cword;
  278.   register unsigned mask;
  279.  
  280.   printf("\n\n\nFirst Derives\n");
  281.  
  282.   for (i = start_symbol; i < nsyms; i++)
  283.     {
  284.       printf("\n%s derives\n", symbol_name[i]);
  285.       rp = first_derives + i * WORDSIZE(nrules);
  286.       cword = *rp++;
  287.       mask = 1;
  288.       for (j = 0; j <= nrules; j++)
  289.         {
  290.       if (cword & mask)
  291.         printf("   %d\n", j);
  292.  
  293.       mask <<= 1;
  294.       if (mask == 0)
  295.         {
  296.           cword = *rp++;
  297.           mask = 1;
  298.         }
  299.     }
  300.     }
  301.  
  302.   fflush(stdout);
  303. }
  304.  
  305. #endif
  306.